import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-06-11
 * Time: 19:07
*/

public class Test{
//     public void rotate(int[] nums, int k) {
//         // time limit
//         // int left = 0;
//         // int right = nums.length-1;
//         // while(k > 0){
//         //     int index = nums[nums.length-1];
//         //     for(int i = nums.length-1; i > 0; i--){
//         //         nums[i] = nums[i-1];
//         //     }
//         //     nums[0] = index;
//         //     k--;
//         // }
//         int left = 0;
//         int right = nums.length - 1;
//         k %= nums.length;
//         while(left < right){
//             //整体翻转一次
//             int tmp = nums[right];
//             nums[right] = nums[left];
//             nums[left] = tmp;
//             left++;
//             right--;
//         }
//         //[0,k-1][k,nums-1]
//         left = 0;
//         right = k-1;
//         while(left < right){
//             //轮转的部分再翻转一次
//             int tmp = nums[right];
//             nums[right] = nums[left];
//             nums[left] = tmp;
//             left++;
//             right--;
//         }
//         left = k;
//         right = nums.length-1;
//         while(left < right){
//             //剩余部分再翻转一次
//             int tmp = nums[right];
//             nums[right] = nums[left];
//             nums[left] = tmp;
//             left++;
//             right--;
//         }
//     }
    //翻转数组法
        public static void rotate1(int[] nums, int k) {
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }

        public static void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }
        //数学推导 -》 挨个交换到正确位置
        public static void rotate(int[] nums, int k) {
            int n = nums.length;
            k = k % n;//防止k > n
            int count = gcd(k,n);//当每个数都交换到正确的位置时（也就是交换次数等于n）就停止循环，n/count就是每次交换的次数
            /**
             * count的由来：因为从 0 开始不断遍历，最终又回到起点 0，这个过程走了a圈（a正为整数），
             * 每圈的长度为n。 这个过程中，走的每一步的长度为k,共走过了b个元素，所以走的总步长为bk，
             * 也即这a圈的长度，即a*n=b*k。 即 a*n 一定为 n,k 的公倍数。又因为我们在第一次回到起
             * 点时就要结束，因此a要最小，故a*n就是n,k的最小公倍数lcm(n,k) ， 因此 b 就为lcm(n,k)/k，
             * 这说明从起点再次回到起点的过程中会访问到 lcm(n,k)/k 个元素。 为了访问到所有的元素，
             * 我们需要进行遍历的次数为，n/lcm(n,k)/k = n*k/lcm(n,k) = gcd(n,k)(最大公约数
             * 和最小公倍数的关系) 即需要遍历的次数为n和k的最大公约数。
             *
             * !!!最主要还是画图理解
             */
            for(int start = 0; start < count; start++){
                int perv = nums[start];
                int current = start;
                do{
                    int next = (current + k) % n;
                    int tmp = nums[next];
                    nums[next] = perv;
                    perv = tmp;
                    current = next;
                }while(start != current);
            }
        }
        //求最大公约数
        public static int gcd(int x,int y){
            return y > 0 ? gcd(y,x % y):x;
        }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        int k = 3;
        rotate(nums,k);
    }
    public static int[] sortedSquares(int[] nums) {

        int left = 0;
        int right = nums.length-1;
        int[] arr = new int[nums.length];
        int i = 0;
        while(left < right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                arr[i] = nums[left]*nums[left];
                left++;
                i++;
            }else{
                arr[i] = nums[right]*nums[right];
                right--;
                i++;
            }
        }
        int l = 0;
        int r = arr.length - 1;
        while(l < r){
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
        return arr;
    }

    public static void main2(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(Arrays.toString(sortedSquares(nums)));
    }
    public static int search(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    public static void main1(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 9;
        System.out.println(search(nums, target));
    }
}
